package algorithms.roughgarden.part2.dynamicprogramming.allpair;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

import algorithms.common.CommonIOUtil;
import static java.lang.Integer.*;


public class Main {

	private static final String INPUT_FILE_NAME = "g3.txt";
	private static final String DELIMITER=" ";
	private static int noOfVertices;
	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		//NEED to improve the speed. It took around 5 mins on single graph g3
		//g1 and g2 have negative cycles as found using one iteration and hasCycles method of graph, so not running algorithm there
		Graph inputGraph = initializeFromInputFile(INPUT_FILE_NAME);
		int[] minShortestArr = new int[noOfVertices];
		int minTemp;
		//Running algorithm multiple times to calculate All Pair Shortest Paths using Bellman Ford as work horse
		//However, it is too slow but for Floyd Warshall cubic array was not fitting on Heap
		for(int i=1;i<noOfVertices;i++){
			minTemp = CommonIOUtil.minimumElement(inputGraph.getShortestDistanceFromSource(i));
			minShortestArr[i-1] = minTemp;
			//System.out.println(i+":"+minTemp);
			inputGraph.resetGraph();
		}
		System.out.println(CommonIOUtil.minimumElement(minShortestArr));
	}
	
	private static Graph initializeFromInputFile(String inputFileName) throws NumberFormatException, IOException{
		InputStream is = Main.class.getResourceAsStream(INPUT_FILE_NAME);
		BufferedReader br = new BufferedReader(new InputStreamReader(is));
		String str;
		str = br.readLine();
		String[] strArr = str.split(DELIMITER);
		noOfVertices = Integer.parseInt(strArr[0]);
		Graph inputGraph = new Graph(noOfVertices, Integer.parseInt(strArr[1]));
		while((str = br.readLine())!=null){
			strArr = str.split(DELIMITER);
			inputGraph.addEdge(parseInt(strArr[0]), parseInt(strArr[1]), parseInt(strArr[2]));
		}
		
		return inputGraph;
	}

}
